//移除链表元素
/*给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* _head = new ListNode(-1, head);
        ListNode* p = _head;
        while (head) {
            if (head->val == val) {
                p->next = head->next;
            } else {
                p = head;
            }
            head = head->next;
        }
        return _head->next;
    }
};


//多数元素
/*给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。*/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int mid = nums.size() / 2;
        return nums[mid];
    }
};

//轮转数组
/*给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。*/
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % (nums.size());
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

//买卖股票的最佳时机
/*给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = INT_MAX;
        int max_count = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else
                max_count = max(max_count, prices[i] - minprice);
        }
        return max_count;
    }
};


//买卖股票的最佳时机 II
/*给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX;
        int count = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] < min_price)
                min_price = prices[i];
            else {
                count += prices[i] - min_price;
                min_price = prices[i];
            }
        }
        return count;
    }
};

//跳跃游戏
/*给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。*/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        // vector<int> ret(nums.size());
        //  if (nums.size() == 1)
        //    return true;
        int max_g = nums[0];
        // ret[0] = nums[0];
        for (int i = 0; i <= max_g; i++) {
            max_g = max(nums[i] + i, max_g);
            if (max_g >= nums.size() - 1)
                return true;
        }
        return false;
    }
};